package com.dy.分类.递归回溯分治.全排列;

import java.util.LinkedList;
import java.util.List;

class Solution {

    public   List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new LinkedList<>();
        if(nums.length==0){
            return res;
        }
        digui(0,nums,res);
        return res;
    }

    void digui(int begin,int[] nums,List<List<Integer>>  res){
        //最后一个位置不需要交换
        if(begin==nums.length-1){
            List<Integer> list = new LinkedList<>();
            for(int i=0;i<nums.length;i++){
                list.add(nums[i]);
            }
            res.add(list);
            return ;
        }
        for(int i=begin;i<nums.length;i++){
            swap(nums,begin,i);
            digui(begin+1,nums,res);
            swap(nums,begin,i);
        }
    }

    void swap(int[] nums,int j,int i){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int nums[ ] = {1,2,3};
        solution.permute(nums);
    }
}